package com.agile.leetcode.hot.easy.dynamicprogramming;

/**
 * @Author:ChenZhangKun
 * @Date: 2021/11/14 16:53
 */
public class MaxSubArray {
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(arr));
        System.out.println(maxMultiArray(arr));
    }

    /**
     * 最大连续子数组和
     *
     * @param arr
     * @return
     */
    public static Integer maxSubArray(int[] arr) {
        // 创建dp数组
        int[] dp = new int[arr.length];
        // 初始化
        dp[0] = arr[0];
        // 定义接收
        int max = arr[0];
        // 遍历数组
        for (int i = 1; i < arr.length; i++) {
            // 状态转移
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }

    /**
     * 连续子数组的最大乘积
     *
     * @param arr
     * @return
     */
    public static Integer maxMultiArray(int[] arr) {
        int[] dpmin = new int[arr.length];
        int[] dpmax = new int[arr.length];
        dpmin[0] = arr[0];
        dpmax[0] = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            // 记录最大值
            dpmax[i] = max(dpmax[i - 1] * arr[i], dpmin[i - 1] * arr[i], arr[i]);
            // 记录最小值
            dpmin[i] = min(dpmax[i - 1] * arr[i], dpmin[i - 1] * arr[i], arr[i]);
            // 拿到最大的绝对值
            max = Math.max(max, Math.max(Math.abs(dpmax[i]), Math.abs(dpmin[i])));
        }
        return max;
    }

    /**
     * 三数最大值
     *
     * @param i
     * @param i1
     * @param i2
     * @return
     */
    private static int max(int i, int i1, int i2) {
        return Math.max(Math.max(i, i1), i2);
    }

    /**
     * 三数最小值
     *
     * @param i
     * @param i1
     * @param i2
     * @return
     */
    private static int min(int i, int i1, int i2) {
        return Math.min(Math.min(i, i1), i2);
    }
}
